package com.softfly.timu;

import java.util.ArrayList;
import java.util.List;

public class Timu0077 {

    private void dfs(int cur, int n, int k, List<Integer> temp, List<List<Integer>> ans) {
        if (temp.size() + n - cur + 1 < k) {
            return;
        }

        if (temp.size() == k) {
            List<Integer> record = new ArrayList<>();
            record.addAll(temp);
            ans.add(record);
            return;
        }

        temp.add(cur);
        dfs(cur + 1, n, k, temp, ans);

        temp.remove(temp.size() - 1);
        dfs(cur + 1, n, k, temp, ans);

    }

    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        dfs(1, n, k, temp, ans);
        return ans;
    }


    public static void main(String[] args) {
        System.out.println(new Timu0077().combine(4, 2));
    }
}
